//平衡二叉树
class Solution4 {
    //时间复杂度O(n)
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        return maxDepth(root)>=0;
    }
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        //求左子树的深度
        int leftHeight = maxDepth(root.left);
        if(leftHeight<0){
            return -1;
        }
        //求右子树的深度
        int rightHeight = maxDepth(root.right);
        if(rightHeight<0){
            return -1;
        }
        //当左子树的深度-右子树的深度的绝对值<=1 && 左子树是平衡的 && 右子树是平衡的 才会返回真正的值
        if(Math.abs(leftHeight-rightHeight)<=1 && leftHeight>= 0 && rightHeight>=0){
            return Math.max(leftHeight,rightHeight)+1;
        }else{
            return -1;
        }
    }
}